#include<iostream>
#include<vector>
using namespace std;

namespace STL
{
	template<class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};
	template<class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	private:
		Container _con;
		Compare _com;
	private:
		int parent(int i) { return (i - 1) / 2; }
		int leftchild(int i) { return i * 2 + 1; }
		int rightchild(int i) { return i * 2 + 2; }
		void AdjustUp(int index)
		{
			while (index > 0)
			{
				int p = parent(index);
				if (_com(_con[p], _con[index]))
				{
					swap(_con[p], _con[index]);
					index = p;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(int index)
		{
			int l = leftchild(index);
			int r = rightchild(index);
			int temp = index;
			if (l < _con.size() && _com(_con[temp], _con[l]))temp = l;
			if (r < _con.size() && _com(_con[temp], _con[r]))temp = r;
			if (index != temp)
			{
				swap(_con[index], _con[temp]);
				index = temp;
				AdjustDown(index);
			}
		}
	public:
		void push(const T& val)
		{
			_con.push_back(val);
			AdjustUp(_con.size() - 1);
		}
		void pop()
		{
			if (!_con.empty())
			{
				swap(_con[0], _con[_con.size() - 1]);
				_con.pop_back();
				AdjustDown(0);
			}
		}
		T& top()
		{
			return _con[0];
		}
		const T& top()const
		{
			return _con[0];
		}
		size_t size()const
		{
			return _con.size();
		}
		bool empty()const
		{
			return _con.empty();
		}
	};
}

	int main()
	{
		STL::priority_queue<int> q;
		q.push(3);
		q.push(6);
		q.push(0);
		q.push(1);
		q.push(2);
		q.push(5);
		q.push(7);
		q.push(8);
		q.push(4);
		q.push(9);
		while (!q.empty())
		{
			cout << q.top() << " ";
			q.pop();
		}
		cout << endl;
		return 0;
	}
